class QuickSort {
  /**
   * quick sort class
   * @param list {any[]}
   */
  constructor(list) {
    this.list = list
  }

  partition(low, high, getValue) {
    const first = this.list[low]
    while (low < high) {
      while (low < high && getValue(first) <= getValue(this.list[high])) {
        high--
      }
      this.list[low] = this.list[high]
      while (low < high && getValue(this.list[low]) <= getValue(first)) {
        low++
      }
      this.list[high] = this.list[low]
    }
    this.list[low] = first
    return low
  }

  qSort(low, high, getValue) {
    const args = [low, high]
    /**
     * 循环调用解决递归栈溢出，下面一种有调用栈溢出风险
     */
    while (args.length > 0) {
      const [low, high] = args.splice(0, 2)
      if (low < high) {
        const partitionKey = this.partition(low, high, getValue)
        args.push(low, partitionKey - 1, partitionKey + 1, high)
      }
    }
    // if (low < high) {
    //   const partitionKey = this.partition(low, high, getValue)
    //   this.qSort(low, partitionKey - 1, getValue)
    //   this.qSort(partitionKey + 1, high, getValue)
    // }
  }

  sort(getValue) {
    const low = 0
    const high = this.list.length - 1
    this.qSort(low, high, getValue)
    return this.list
  }
}

module.exports = QuickSort

const test = [9, 17, 0, 93, 1, 88, 5, 2, 66, 10]

const quickSort = new QuickSort(test)

console.log(quickSort.sort((item) => item))
